1. Field of the Invention
This invention relates in general to the field of electronic circuit devices, and more particularly to an apparatus and method for performing both forward and inverse compact Haar Transforms.
2. Description of the Related Art
The characteristics and behavior of electronic signals can be expressed in a number of different ways, but perhaps the most common way of representing a signal is by plotting its amplitude as a function of time, or as a function of distance from a point, or as a function of some other variable relevant to the signal. Mathematically speaking, the domain of the signal corresponds to the relevant variable, say, time. The range of the signal corresponds to its amplitude. Consequently, signals are classified according to their domain. For example, a signal having time as its domain is known as a time domain signal.
The expression and manipulation of signals in the time domain are performed every day in virtually every electronic product. This is because real events affecting most electronic products occur in real time. Radio signals are modulated by electronic modulators in real-time, modulated signals are transmitted in real time, transmitted signals are received and demodulated in real time, demodulated signals are converted by electronic transducers into audio tones in real time, and audio tones are heard by listeners in real time.
Time domain signals are useful and familiar, but many applications, specifically applications that handle or manipulate lots of data, can be better served by transforming a time domain signal into another form, that is, representing the signal within another domain. For example, some operations or computations by an electronic product may require less logic or may be performed much faster on signals that have been transformed into another domain. More specifically, a signal in an original domain, say time, is first transformed into a representation of the signal in a transform domain, say frequency. Next, desired operations or computations are performed on the frequency domain signal to produce a frequency domain output. Finally, an inverse transformation is performed on the frequency domain output to yield a time domain output.
The Fourier transform is perhaps the most well-known transform that is used within electronic products for purposes described above. Executing a Fourier transform on a time domain signal so that it is represented in the frequency domain immediately provides two benefits that cannot easily be achieved in the time domain: 1) the frequency characteristics of the signal, that is, which frequencies are stronger and which are weaker, can be clearly observed from a frequency domain plot of the signal; and 2) convolution of the signal with another signal to produce a result becomes a simple multiplication operation. In the first case for example, it is difficult to determine from a time domain representation of a 25 Hz sinusoidal waveform that its fundamental frequency is 25 Hz. Yet, after transformation to the frequency domain, the 25-Hz fundamental frequency is immediately apparent. In the second case, passing a time domain signal through a low pass filter produces an output signal. But to determine the structure of the output signal requires that a convolution integral be computed using the time domain signal and the impulse response of the low pass filter. A convolution calculation is a very tedious and complex process. Yet, the filter output can more easily be determined by multiplying the Fourier transform of the input signal by the Fourier transform of the filter impulse response, and then performing an inverse transform on the result of the multiplication.
There are many other types of transforms used in electronic products today. Typically, a specific transform is used for a specific application because it provides certain benefits such as speed, observation of some signal parameter, or reduction in logic. One particular transform that provides both logic reduction benefits as well as computational ease is the Haar transform. A class of signals, smooth signals, require less logic within an electronic device to store and manipulate when they are represented in the Haar domain as opposed to their original domain. Effectively, less bits are required to store a Haar domain parameters than would be required to store signal parameters in the original domain, thus compressing the signal data.
That data compression is achieved for smooth signals using Haar transform techniques is not inconsequential because reduction in the logic required to store signal parameters in electronic devices directly reduces the amount of power required to operate the devices. In addition, logic reduction typically reduces the cost of a product because it uses less components. This is very important when one considers the vast number of hand-held and portable products in use today because these devices are powered by batteries. Consequently, reducing the number of logic cells within a portable device means that it can operate longer, or that a smaller battery can be used to achieve equivalent operating time.
But the Haar transform is not used in many applications where data compression can be achieved because the number of bits that are required to express a signal in the Haar domain increases in proportion to the number of data samples that are transformed from the original domain to the Haar domain. More specifically, for a sequence of 256 samples of a signal where each of the samples requires 10 bits to express in the original domain requires 18-bit registers to compute the 256 Haar parameters needed to express the signal in the Haar domain. Once the signal is transformed into the Haar domain, if it is sufficiently smooth, one finds that most of the Haar parameters that result have zeros in most of the bit positions of the parameter registers. But in order to compute the parameters in the first place, 18-bit registers are required.
In general, the number of bits required to compute Haar parameters is equal to the base 2 log of the number of input samples plus the number of bits required to express each of the input samples. For M n-bit data samples, computation of corresponding Haar parameters requires registers that are log2M+n bits wide. In the case of 1,024 10-bit samples, the register size required to compute corresponding Haar parameters is twice the size of that required to store the original samples.
Therefore, what is needed is a forward Haar transform apparatus that does not require an excessive number of bits for computation of Haar parameters corresponding to an input sequence of data samples.
In addition, what is needed is an inverse Haar transform apparatus that can perform an inverse Haar transform on a set of bit-limited Haar parameters to produce an output in the original domain.
Furthermore, what is need is a method for performing forward and inverse Haar transforms on a sequence of n-bit data samples, where calculation of the corresponding Haar parameters requires at most n+1-bit registers.
To address the above-detailed deficiencies, it is an object of the present invention to provide a forward Haar transform apparatus that requires at most n+1-bit registers to compute Haar parameters corresponding to an input sequence of n-bit data samples. Accordingly, in the attainment of the aforementioned object, it is a feature of the present invention to provide a compact Haar transform apparatus, for executing a spectral transformation corresponding to a sequence of n-bit samples. The compact Haar transform apparatus includes sum-and-truncate logic and a plurality of coefficient generators. The sum-and-truncate logic generates a plurality of n-bit intermediate terms where the sum-and-truncate logic truncates the least significant bit of a generated n+1-bit sum to form an associated n-bit intermediate term. The a plurality of coefficient generators is coupled to the sum-and-truncate logic. The plurality of coefficient generators generates a plurality of n+1-bit spectral coefficients, where the associated n-bit intermediate term corresponds to one of the plurality of n+1-bit spectral coefficients. The one of the plurality of n+1-bit spectral coefficients indicates whether the generated n+1-bit sum was even or odd. The generated n+1-bit sum is restored by adding the least significant bit of said the of the plurality of n+1-bit spectral coefficients to the associated n-bit intermediate term.
An advantage of the present invention is that the number of logic cells required to implement a forward Haar transform is much less than what has heretofore been provided.
Another object of the present invention is to provide an inverse Haar transform apparatus that can perform an inverse Haar transform on a set of n+1-bit Haar parameters to produce an output in the original domain consisting of n-bit data samples.
In another aspect, it is a feature of the present invention to provide an apparatus for executing a compact Haar transform. The apparatus has an index signal and inverse transform logic. The index signal indicates a specific n-bit sample. The specific n-bit sample is one of a sequence of n-bit samples corresponding to the compact Haar transform. The inverse transform logic is coupled to the index signal, and computes the specific n-bit sample. The specific n-bit sample is derived from selected n+l-bit spectral coefficients. The inverse transform logic includes a rank decoder, coefficient negation logic, and LSB restoral logic. The rank decoder decodes the index signal to provide one of the selected n+1-bit spectral coefficients, where the one of said selected n+l-bit spectral coefficients corresponds to a compact Haar spectral rank, and where the rank decoder includes a read only memory (ROM). The coefficient negation logic is coupled to the rank decoder. The coefficient negation logic negates the one of the selected n+1-bit spectral coefficients based upon the state of a bit of the index signal, where the state of the bit of the index signal indicates whether a Haar basis function corresponding to the one of the selected n+1-bit spectral coefficients is positive or negative. The LSB restoral logic is coupled to the rank decoder. The LSB restoral logic adds a least significant bit of the one of the selected n+1-bit spectral coefficients into an n-bit sample computation, where the n-bit sample computation is required to compute the n-bit sample.
Another advantage of the present invention is that a set of common logic devices can be used to compute an inverse Haar transform because all of the Haar coefficients are within one bit of the width of an output sample.
In a further aspect, it is a feature of the present invention to provide a computer program product for use in designing, simulating, fabricating, or testing a compact Haar transform circuit. The computer program product has a storage medium. The storage medium, has computer readable instructions embodied thereon, for causing a computer upon which the computer readable instructions are executed to describe the compact Haar transform circuit such that it can be modified, simulated, fabricated, or tested. The computer readable instructions include first instructions. The first instructions cause the computer to describe inverse Haar transform logic. The inverse Haar transform logic is configured to compute n-bit samples, where each of the n-bit samples is derived from n+1-bit spectral coefficients. The inverse transform logic has a rank decoder, a coefficient negator, and LSB restoral logic. The rank decoder receives an index signal from a source thereof, and provides one of the n+1-bit spectral coefficients, the one of the n+1-bit spectral coefficients corresponding to a rank of a compact Haar spectrum. The coefficient negator is coupled to the rank decoder, and negates the one of the n+l-bit spectral coefficients based upon the state of a bit of the index signal. The LSB restoral logic is coupled to the rank decoder. The LSB restoral logic adds a least significant bit of the one of the n+1-bit spectral coefficients into an n-bit sample computation, where the n-bit sample computation is required to generate a particular n-bit sample.
A further advantage of the present invention is that less power is required to operate an electronic device that employs the compact Haar transform technique.
Yet another object of the present invention is to provide a method for performing forward and inverse Haar transforms on a sequence of n-bit data samples, where calculation of the corresponding Haar parameters requires at most n+1-bit registers.
In yet a further aspect, it is a feature of the present invention to provide a method for executing an inverse compact Haar transform. The method includes decoding an index to select n+1-bit spectral coefficients, the n+1-bit spectral coefficients being required to compute a specific n-bit data sample; negating those n+1-bit spectral coefficients whose corresponding Haar basis function is negative for the index provided by the decoding; computing a sum of the negated n+1-bit spectral coefficients with the selected n+1-bit spectral coefficients which are not negated by the negating; and adding the least significant bits of all of the selected n+l-bit spectral coefficients to the sum produced by the computing.
Yet a further advantage of the present invention is that less complex logic devices can be employed within electronic products to perform forward and inverse Haar transformations.